#define _CRT_SECURE_NO_WANINGS 1
#pragma warning(disable: 4996)
class Partition {
public:
    ListNode* partition(ListNode* phead, int x) {
        ListNode* cur = phead;
        ListNode* biglist = nullptr;
        ListNode* smllist = nullptr;
        ListNode* bhead = nullptr;
        ListNode* shead = nullptr;
        if (phead == nullptr)
        {
            return nullptr;
        }
        while (cur) {
            if (cur->val <= x) {
                if (smllist == nullptr) {
                    shead = smllist = cur;
                }
                else {
                    smllist->next = cur;
                    smllist = smllist->next;
                }
            }
            else {
                if (biglist == nullptr) {
                    bhead = biglist = cur;
                }
                else {
                    biglist->next = cur;
                    biglist = biglist->next;
                }
            }
            cur = cur->next;
        }
        smllist->next = bhead;
        return shead;
    }
};